'''
https://leetcode.cn/problems/shortest-bridge/description/?envType=study-plan-v2&envId=graph-theory
'''
from collections import deque
from typing import List


class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = []
        def dfs(i, j):
            grid[i][j] = -1
            q.append((i, j))
            for tx, ty in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 1:
                    dfs(tx, ty)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dfs(i, j)
                    step = 0
                    while True:
                        temp = []       # !!!
                        for _ in range(len(q)):
                            i, j = q.pop()
                            if grid[i][j] == 1:
                                return step - 1
                            for tx, ty in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
                                if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] != -1:
                                    temp.append((tx,ty))
                                    grid[i][j] = -1
                        q = temp
                        step += 1

grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
print(Solution().shortestBridge(grid))